NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/12308

Internet Message Format | 1996-08-05 | 4.7 KB

Path: beta.nedernet.nl!usenet
From: [e-mail] (Jos A. Horsmeier)
Newsgroups: comp.lang.c
Subject: How about some theory? (was: Re: "Best fit" algorithm (help))
Date: 30 Mar 1996 13:05:32 GMT
Organization: AND Operations Research B.V.
Message-ID: <4jjbis$[e-mail]>
References: <APC&7'0'22b6b83'[e-mail]> <4jhlu7$[e-mail]>
NNTP-Posting-Host: klepzeiker.and.nl
Mime-Version: 1.0
Content-Type: Text/Plain; charset=ISO-8859-1
X-Newsreader: WinVN 0.99.5

In article <4jhlu7$[e-mail]>, [e-mail] wrote:
|[e-mail]:

|> I am looking for a "best fit" algorithm.
|> The problem I have is very similar to finding the best way of fitting the
|> maximum number of songs on (say) 45 minute tape.

|  I used to have a program like that for my C64, the guy that wrote it said
|the most effective method he found was trying random combinations.

IMHO your friend didn't look hard enough then. I agree, the original poster
was a bit ambiguous when he posed the question (not shown above), but still,
we're talking about optimization here. The original question implied two
optimization problems:

1: how to arrange for the maximum _number_ of songs on a tape;
2: how to _minimize_ the amount of unused tape.

The first question is easy to solve: start recording the shortest songs
and proceed recording the next song in the row (sorted) until the song to
be recorded doesn't fit on the tape anymore.

A random search (as your friend proposed) doesn't bring you much; it's like
wandering around in a foggy mountain landscape, searching for the steepest
valley; Walking around randomly involves 'uphill steps' with no indication
whether or not that step would do any good in finding the 'optimal',
solution, i.e. finding the steepest valley. On the other hand: going
'downhill' randomly doesn't buy you much either;  you might end up
in a valley far away (and far above) the 'optimal' valley.

Even a 'steepest downhill' step doesn't help you out unless the problem
satisfies quite a nasty criterion: it has to be convex. The first problem
happens to be convex and a steepest downhill step (maximizing the amount
of unused tape after recording a song) brings you down to the deepest
valley, i.e. the maximum _number_ of songs recorded on tape, as fast as
possible.

The second problem is much more 'fun' (mind the quotes, only operations
research afficionados would leave out the quotes ;-) On first inspection
of the problem, there's nothing else we can do but enumerate all possible
combinations of songs and see which one leaves the minimum amount of
unused tape left. Luckily enough, those same or-afficionados took a second
look and came up with the following idea:

- let d be the duration of the tape;
- let l[i] be the length of the i-th song;
- if somebody told us that song i happens to be an in the optimal set of
  songs, then we can take advantage of it, by solving a smaller problem,
  i.e. the duration of tape equals d-l[i] and the number of songs is
  reduced by one (song i is removed from the problem set).

The last observation brings us back to square one again. The only
advantage we have is, that we're dealing with a smaller problem here.
If we apply the same reasoning to this problem again (did anyone say
'recursion'?) we end up with a very simple problem; we either have
no songs left and (possibly) a bit of tape left or we have a song left
and not enough tape left to record that song.

Let's sprinkle some math lingo over this little problem:

let d be the duration of the tape and let S be the set of songs. Let
l[i] be the duration of the i-th song again. Our problem can be denoted
as O(d, S) (the 'O' stands for 'optimal' here, not for 'big-oh').

Applying the observations described above, we can deduce:

    O(d, S) = min (for all i where l[i] <= d: O(d-l[i], S-i))

The recurrent expression shown above doesn't take that much programming
skill to implement. (I've already given the corresponding C functions
in another reply). But here's my question: why don't people try to
utilize some theory they've been forced to study when they were students,
before trying to implement algorithms that are supposed to do the job?

Don't people read books anymore? Do people like to jump in front of one
of those silly terminals/PCs/work stations/whatever right after listening
or reading about the problem to be solved without _thinking_ about it
a bit before starting typing 'void main()' or whatever and moving that
silly mouse all over their desk as if it were their favority Dinky Toy?
I'm quite pessimistic about the answer to these questions ...

Or maybe I'm just getting old ... (no Dik, don't answer ;-)

kind regards,

Jos aka [e-mail]
--
Atnwgqkrl gy zit vgksr, ug qshiqwtzoeqs!